package algorithm.MaxSubarrSum;

/*
给定一个二维数组arr，返回子矩阵的最大累加和
 */
public class MaxSubarr2DSum {
    public static int MaxSum(int[][] arr) {
        if (arr.length == 0 || arr[0].length == 0)
            return 0;

        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {  //以i行开头
            int[] compact = new int[arr[0].length];
            for (int j = i; j < arr.length; j++) {  //以j行结尾
                //压缩数组至一维
//                int[] compact = arrCompact(i, j, arr);
                for (int k = 0; k < arr[0].length; k++) {  //列
                    compact[k] += arr[j][k];
                }
                int sum1D = sum1D(compact);
                max = Math.max(max, sum1D);
            }
        }
        return max;
    }

    public static int sum1D(int[] arr) {
        int max = Integer.MIN_VALUE;
        int cur = 0;
        for (int i = 0; i < arr.length; i++) {
            cur += arr[i];
            if (cur < 0)
                cur = 0;
            max = Math.max(max, cur);
        }
        return max;
    }

    public static void main(String[] args) {
        int[][] arr = {{90, 48, 47},
                        {64, -40, 64},
                        {-81, -7, 66}};
        System.out.println(MaxSum(arr));
    }
}
